package structures.tree2;

public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        String[] array = {"A", "B", "C", "D", "E", "F", "G", "H"};
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        Node root = threadedBinaryTree.createBinaryTree(array);
        threadedBinaryTree.preThreadedOrder(root);
        threadedBinaryTree.preThreadedList(root);
    }
}

class ThreadedBinaryTree {

    public Node createBinaryTree(String[] array) {
        return createBinaryTree(array, 0);
    }

    /**
     * 根据数组创建二叉树
     *
     * @param array
     * @param index
     * @return
     */
    private Node createBinaryTree(String[] array, int index) {
        if (array == null || array.length == 0 || array.length <= index) {
            return null;
        }

        Node node = new Node(array[index]);
        node.setLeftNode(createBinaryTree(array, index * 2 + 1));
        node.setRightNode(createBinaryTree(array, index * 2 + 2));
        return node;
    }

    private Node preNode = null;

    /**
     * 前序线索化二叉树
     *
     * @param node
     */
    public void preThreadedOrder(Node node) {
        if (node == null) {
            return;
        }

        if (node.getLeftNode() == null) {
            node.setLeftNode(preNode);
            node.setLeftType(true);
        }
        if (preNode != null && preNode.getRightNode() == null) {
            preNode.setRightNode(node);
            preNode.setRightType(true);
        }
        preNode = node;
        if (!node.isLeftType()) {
            preThreadedOrder(node.getLeftNode());
        }
        if (!node.isRightType()) {
            preThreadedOrder(node.getRightNode());
        }
    }

    public void preThreadedList(Node node) {
        while (node != null) {
            while (!node.isLeftType()) {
                System.out.println(node);
                node = node.getLeftNode();
            }
            System.out.println(node);
            node = node.getRightNode();
        }
    }

    /**
     * 中序 线索化二叉树
     *
     * @param node
     */
    public void infixThreadedOrder(Node node) {
        if (node == null) {
            return;
        }

        infixThreadedOrder(node.getLeftNode());

        if (node.getLeftNode() == null) {
            node.setLeftNode(preNode);
            node.setLeftType(true);
        }

        if (preNode != null && preNode.getRightNode() == null) {
            preNode.setRightNode(node);
            preNode.setRightType(true);
        }
        preNode = node;

        infixThreadedOrder(node.getRightNode());


    }

    /**
     * 中序遍历
     *
     * @param node
     */
    public void infixThreadedList(Node node) {
        while (node != null) {
            while (!node.isLeftType()) {
                node = node.getLeftNode();
            }
            System.out.println(node);

            while (node.isRightType()) {
                node = node.getRightNode();
                System.out.println(node);
            }

            node = node.getRightNode();
        }
    }
}

class Node {
    private String data;
    private Node leftNode;
    private Node rightNode;
    // false: 左节点   true: 前驱线索
    private boolean leftType = false;
    // false: 又结点   true: 后继线索
    private boolean rightType = false;

    public Node(String data) {
        this.data = data;
    }

    public Node getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }

    public Node getRightNode() {
        return rightNode;
    }

    public void setRightNode(Node rightNode) {
        this.rightNode = rightNode;
    }

    public boolean isLeftType() {
        return leftType;
    }

    public void setLeftType(boolean leftType) {
        this.leftType = leftType;
    }

    public boolean isRightType() {
        return rightType;
    }

    public void setRightType(boolean rightType) {
        this.rightType = rightType;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data='" + data + '\'' +
                '}';
    }
}
